package 力扣日常刷题.木22一月.第04天0111;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/11
 * @description
 */
public class Demo04回溯组合 {


    ArrayList<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(0,n,k,new ArrayList<Integer>());
        return ans;
    }


    void dfs(int index,int n,int k,ArrayList<Integer> list){
        // 剪枝
        if(n-index <k) return;
        if(k == 0){
            ans.add(new ArrayList<>(list));
            return ;
        }
        if(index >=n)return ;

        dfs(index+1,n,k,list);
        list.add(index+1);
        dfs(index+1,n,k-1,list);
        list.remove(list.indexOf(index+1));
    }
}
